package ljl.alg.jianzhioffer.round2;

import java.util.LinkedList;

public class _13_robot_move_range {
    
    /***
     * 蒙对了
     * 我有点高兴
     * 虽然十年前我就该会做
     * */
    public int movingCount3(int m, int n, int k) {
        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;
        int res = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && dp[i - 1][j] || j > 0 && dp[i][j - 1])
                    if (ok(i, j, k)) {
                        dp[i][j] = true;
                        res++;
                    }
                    
            }
        }
        return res;
    }
    boolean ok(int i, int j, int k) {
        return count(i) + count(j) <= k;
    }
    int count(int i) {
        int sum = 0;
        while (i > 0) {
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }
    
    /**
     * 没想到这个题还有别的解法。。
     * dfs
     * 这个居然还很快，我透？
     * */
    boolean[][] visited;
    int k;
    int m, n;
    public int movingCount2(int m, int n, int k) {
        this.visited = new boolean[m][n];
        this.k = k;
        this.m = m;
        this.n = n;
        return calc(0, 0, 0, 0);
    }
    int calc(int i, int j, int si, int sj) {
        if (i == m || j == n || visited[i][j] || si + sj > k) return 0;
        visited[i][j] = true;
        return 1 + calc(i + 1, j, (i + 1) % 10 == 0 ? si - 8 : si + 1, sj)
        + calc(i, j + 1, si, (j + 1) % 10 == 0 ? sj - 8 : sj + 1);
    }
    
    
    /**
     * 没想到这个题还有别的解法。。
     * bfs
     *
     * 这个解法比较慢
     * 我感觉主要是构建数组慢
     * 还有入队出队啥的
     * */
    public int movingCount(int m, int n, int k) {
        LinkedList<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        q.offer(new int[]{0, 0, 0, 0});
        int res = 0;
        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int i = poll[0], j = poll[1], si = poll[2], sj = poll[3];
            if (i == m || j == n || visited[i][j] || si + sj > k)
                continue;
            visited[i][j] = true;
            res++;
            q.offer(new int[] {i + 1, j, (i + 1) % 10 == 0 ? si - 8 : si + 1, sj});
            q.offer(new int[] {i, j + 1, si, (j + 1) % 10 == 0 ? sj - 8 : sj + 1});
        }
        return res;
    }
}
